/**
 * \file
 */
#include "precompiled.hpp"
#include "kfs_allocator.hpp"
#include "Exception.hpp"
#include <errno.h>
#include <fstream>
#include <stdexcept>
#include <vector>

using boost::scoped_array;
using std::runtime_error;
using std::vector;
typedef vector<AllocBlockRef> BlockList;

//------------------------------ AllocBlockRef --------------------------------


AllocBlockRef::AllocBlockRef(kfs::Impl* impl, block_index_t block)
:
    block(block),
    impl(impl)
{
}


AllocBlockRef::~AllocBlockRef()
{
    if(block)
        impl->disk_free(block);
}


AllocBlockRef& AllocBlockRef::operator=(AllocBlockRef& other)
{
    swap(*this, other);
    return *this;
}


block_index_t
AllocBlockRef::get() const
{
    return block;
}


block_index_t
AllocBlockRef::release()
{
    block_index_t oldBlock = 0;
    std::swap(block, oldBlock);
    return oldBlock;
}


void swap(AllocBlockRef& o1, AllocBlockRef& o2)
{
    std::swap(o1.block, o2.block);
    std::swap(o1.impl, o2.impl);
}

//------------------------- ContiguousBlockAllocRef ---------------------------


ContiguousAllocBlockRef::ContiguousAllocBlockRef(kfs::Impl* impl,
    block_index_t numBlocks)
: impl(impl)
{
    m_begin = impl-> disk_allocate_contiguous(numBlocks);
    m_end = m_begin + numBlocks;
}


ContiguousAllocBlockRef::Iterator
ContiguousAllocBlockRef::begin()
{
    return Iterator(this, m_begin);
}


ContiguousAllocBlockRef::Iterator
ContiguousAllocBlockRef::end()
{
    return Iterator(this, m_end);
}


void ContiguousAllocBlockRef::release()
{
    m_begin = m_end = 0;
    impl = 0;
}


void swap(ContiguousAllocBlockRef& o1, ContiguousAllocBlockRef& o2)
{
    std::swap(o1.impl,    o2.impl);
    std::swap(o1.m_begin, o2.m_begin);
    std::swap(o1.m_end,   o2.m_end);
}


void ContiguousAllocBlockRef::Iterator::validateDeref()
{
    if(value == blockid_nil)
    {
        throw Exception("%s: attempt to dereference a nil iterator",
            __FUNCTION__);
    }
}


void ContiguousAllocBlockRef::Iterator::validateAdvance()
{
    if(value == blockid_nil)
    {
        throw Exception("%s: attempt to advance a nil iterator",
            __FUNCTION__);
    }
    else if(value == container->m_end)
    {
        throw Exception("%s: attempt to advance beyond the end",
            __FUNCTION__);
    }
}

//-------------------------------- kfs::Impl --------------------------------//


AllocBlockRef
kfs::Impl::disk_allocate()
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());
    block_index_t* bitmap = reinterpret_cast<block_index_t*>(buffer.get());

    for(block_index_t i = 0; i < mb.blockNumBytes/sizeof(block_index_t); ++i)
    {
        block_index_t* const word = bitmap + i;
        for(block_index_t j = 0; j < sizeof(block_index_t)*8; ++j)
        {
            block_index_t const mask = 1 << j;
            if((*word & mask) == 0)
            {
                block_index_t blockNum = (i << 5) | j;
                if(blockNum >= mb.numBlocks)
                {
                    throw Error(ENOSPC, "No space left on device");
                }
                *word |= mask;
                // Commit the allocation to disk.
                kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());
                printf("%-10s: %4u (%3u,%2u)\n","disk_alloc",blockNum,i,j);
                return AllocBlockRef(this, blockNum);
            }
        }
    }
    throw Error(ENOSPC, "No space left on device");
}


// UNTESTED CODE
void
kfs::Impl::disk_allocate(block_index_t const n, BlockList* list)
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());
    block_index_t* bitmap = reinterpret_cast<block_index_t*>(buffer.get());

    list->clear();
    list->reserve(n);

    try
    {
        // Allocate n blocks in memory, but do not commit them.
        vector<block_index_t> list2;
        disk_allocate_help(bitmap, n, &list2);
        // Take ownership of all the blocks at once.
        for(block_index_t i = 0; i < n; ++i)
        {
            list->push_back(AllocBlockRef(this, list2[i]));
        }
        // Commit the allocations
        kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());
    }
    catch(std::exception& e)
    {
        // Free any blocks we already allocated.
        list->clear();
        throw;
    }
}


void
kfs::Impl::disk_allocate_help(block_index_t* bitmap, block_index_t n,
    vector<block_index_t>* list)
{
    block_index_t numFound = 0;
    list->clear();
    list->reserve(n);
    for(block_index_t i = 0; i < mb.blockNumBytes/sizeof(block_index_t); ++i)
    {
        block_index_t* const word = bitmap + i;
        for(block_index_t j = 0; j < sizeof(block_index_t)*8; ++j)
        {
            block_index_t const mask = 1 << j;
            if((*word & mask) == 0)
            {
                block_index_t blockNum = (i << 5) | j;
                if(blockNum >= mb.numBlocks)
                {
                    throw Error(ENOSPC, "No space left on device");
                }
                list->push_back(blockNum);
                *word |= mask;
                ++numFound;
                if(numFound == n)
                {
                    assert(list->size() == n);
                    return;
                }
            }
        }
    }
    throw Error(ENOSPC, "No space left on device");
}


// UNTESTED CODE
block_index_t
kfs::Impl::disk_allocate_contiguous(block_index_t n)
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());
    block_index_t* bitmap = reinterpret_cast<block_index_t*>(buffer.get());
    block_index_t begin = 0, end = 0;

    for(block_index_t i = 0; i < mb.blockNumBytes/sizeof(block_index_t); ++i)
    {
        block_index_t* const word = bitmap + i;
        for(block_index_t j = 0; j < sizeof(block_index_t)*8; ++j)
        {
            block_index_t mask = 1 << j;
            bool isFree = (*word & mask) == 0;
            block_index_t blockNum = (i << 5) | j;
            if(blockNum >= mb.numBlocks)
            {
                throw Error(ENOSPC, "No space left on device");
            }
            if(begin == 0)
            {
                if(isFree)
                {
                    begin = blockNum; end = blockNum + 1;
                }
            }
            else if(end - begin != n)
            {
                if(isFree)
                {
                    ++end;
                }
                else
                {
                    begin = end = 0;
                }
            }
            else
            {
                i = mb.blockNumBytes/sizeof(block_index_t);
                break;
            }
        }
    }
    if(end - begin != n)
    {
        //todo
        throw Error(ENOSPC, "No space left on device");
    }

    for(block_index_t blockNum = begin; blockNum < end; ++blockNum)
    {
        block_index_t i = blockNum >> 5;
        block_index_t j = blockNum & ((1 << 5) - 1);
        block_index_t* const word = bitmap + i;
        block_index_t mask = 1 << j;
        *word |= mask;
        printf("%-10s: %4u (%3u,%2u)\n","disk_alloc", blockNum,i,j);
    }
    kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());
    return begin;
}


/*(
void kfs::Impl::disk_alloc_commit(block_index_t blockNum)
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());

    block_index_t i = blockNum >> 5;
    block_index_t j = blockNum & ((1 << 5) - 1);
    block_index_t* const word = bitmap + i;
    block_index_t mask = 1 << j;
    *word |= mask;
    kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());
}
*/


void kfs::Impl::disk_free(block_index_t const blockNum)
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());
    block_index_t* bitmap = reinterpret_cast<block_index_t*>(buffer.get());

    block_index_t i = blockNum >> 5;
    block_index_t j = blockNum & ((1 << 5) - 1);
    block_index_t mask = 1 << j;
    if((bitmap[i] & mask) == 0)
        throw runtime_error("disk_free: block is not allocated");
    bitmap[i] &= ~mask;
    kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());

    // DEBUG: Erase the block's data.
    memset(buffer.get(), 0xFE, mb.blockNumBytes);
    kfs_disk_write( *this, blockNum, buffer.get() );

    printf("%-10s: %4u (%3u,%2u)\n",__FUNCTION__,blockNum,i,j);
}


// UNTESTED CODE
template<typename iterator>
void kfs::Impl::disk_free(iterator const begin, iterator const end)
{
    scoped_array<uint8_t> buffer(createBlockBuffer());
    kfs_disk_read(*this, bitmapDiskBlockNum, buffer.get());
    block_index_t* bitmap = reinterpret_cast<block_index_t*>(buffer.get());

    for(iterator iter = begin; iter != end; ++iter)
    {
        block_index_t blockNum = *iter;
        block_index_t i = blockNum >> 5;
        block_index_t j = blockNum & ((1 << 5) - 1);
        block_index_t mask = 1 << j;
        if((bitmap[i] & mask) == 0)
            throw runtime_error("disk_free: block is not allocated");
        bitmap[i] &= ~mask;

        // DEBUG: Erase the block's data.
        memset(buffer.get(), 0xFE, mb.blockNumBytes);
        kfs_disk_write( *this, blockNum, buffer.get() );

        printf("%-10s: %4u (%3u,%2u)\n",__FUNCTION__,blockNum,i,j);
    }
    kfs_disk_write(*this, bitmapDiskBlockNum, buffer.get());
}
